Research Interests
In general, I try to understand what is easy and what is hard to compute, independently of any particular computer. I work in algorithm design and complexity theory, and I especially like connections between the two subjects. I think about many questions, but a few of them haunt me more than others. Some examples:
Can the existence of an algorithm for a problem be used to prove that other algorithms cannot exist for other problems? Can the nonexistence of algorithms be used to prove that another algorithm correctly solves a problem? (In fact, there are "yes" answers to both questions!)
Does every function implementable with a low memory footprint also have a fast implementation? (Is $P = PSPACE$?)
Could computers themselves help us make progress on answering these questions?
Current PhD Students
Graduated PhD Students
Former Postdocs
About Me
I grew up near the big city of Somerville, Alabama, where there is good fishing in the water and good football on the radio. Further south in Alabama there is a good school for math and science.